/*************************************************************************
	> File Name: 739.每日温度.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:47:57 2021
 ************************************************************************/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize){
    *returnSize = temperaturesSize;
    if (temperaturesSize == 0) return NULL;

    int sta[temperaturesSize], top = 0;
    int *ret = (int *)malloc(sizeof(int) * temperaturesSize);
    memset(ret, 0, sizeof(int) * temperaturesSize);

    for (int i = 0; i < temperaturesSize; i++) {
        while (top && temperatures[i] > temperatures[sta[top - 1]]) {
            ret[sta[top - 1]] = i - sta[top - 1];
            top--;
        }
        sta[top++] = i;
    }
    return ret;
}
